C#和.Net框架

题目

题解

• 注意点
  • 子串和子序列的区别
    • 子串是是连续的
    • 子序列可以不是连续的
      • 比如”pwwkew”中,”pwke”是最长子序列,”wke”是最长子串

滑动窗口

• 通过两个指针$i$,$j$，维护一个区间，保证这个区间的子串中无重复元素。
• 每次迭代的时候$j$向后移动，判断当前j指针的元素在上一次迭代的区间中是否存在。
  • 不存在，$i$不动
  • 存在，$i = find_pos(nums[j]) + 1$
• 每次迭代时更新最长无重复的子串长度。

对于在元素中查询方式有以下三种方法。

朴素循环

• 在判断是否有重复元素时遍历一遍区间内的元素

  class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0)  return 0;
        int i = 0;
        int j = 0;
        int res = 0;
        do
        {
            for(int k =  i; k <j ; ++k)
            {
                if(s[k] == s[j])
                {
                    i = k+1;
                    break;
                }
            }
            res = max(res,j-i+1);
             ++j;
        }while(i < s.size() && j < s.size());
  
        return res;
    }
  };
  

• 时间复杂度:$O(n^{2})$
• 空间复杂度:$O(1)$

哈希表

• 这里需要注意判断元素所对应的下标是否还在当前滑动窗口范围内

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_map<char,int> m;
        int i =0;
        int j = 0;
        int res = 0;
        do
        {
            if( m.find(s[j])!= m.end() && m[s[j]] >= i ) //这里主要要求找到的值要大于等于i
            {
                i = m[s[j]]+1;
                m[s[j]] = j;
            }
            else 
            {
                m[s[j]] = j;
            }

            res = max(res,j-i+1);
            ++j;
        }while(i < s.size() && j < s.size());

        return res;
    }
};

• 时间复杂度:unordered_map:O(n)
• 空间复杂度:O(n)

桶排序

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        int m[128]; //利用ascii来存储下标
        fill(m,m+128,-1);
        int i =0;
        int j = 0;
        int res = 0;
        do
        {
            if(m[s[j]] >= i)  //这里主要要求找到的值要大于等于i
            {              
                i = m[s[j]] + 1;
                m[s[j]] = j;
            }
            else
            {
                m[s[j]] = j;
            }

            res = max(res,j-i+1);
            ++j;
        }while(i < s.size() && j < s.size());

        return res;
    }
};

• 时间复杂度:O(n)
• 空间复杂度:O(1)